package com.buddy.leetcode._04;

import java.math.BigDecimal;
import java.util.Arrays;

/**
 *  两个排序数组的中位数
 *  给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
 *  请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。
 *  示例 1:
 *      nums1 = [1, 3]
 *      nums2 = [2]
 *      中位数是 2.0
 *  示例 2:
 *      nums1 = [1, 2]
 *      nums2 = [3, 4]
 *      中位数是 (2 + 3)/2 = 2.5
 *
 *  中位数，又称中点数，中值。
 *  中数是按顺序排列的一组数据中居于中间位置的数，
 *  即在这组数据中，有一半的数据比他大，有一半的数据比他小，
 *  如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数;
 *  如果观察值有奇数个，通常去中间值作为中数
 *  （注意：中位数和众数不同，众数指最多的数，众数有时不止一个，而中位数只能有一个。）
 */
public class MedianOfTwoSortedArrays {

    public static double myFindMedianSortedArrays(int[] nums1, int[] nums2) {
        //1.合并排序
        //2.取中间值
        int[] nums = new int[nums1.length+nums2.length];
        int n1 = 0;
        int n2 = 0;
        int i=0;
        while(nums1.length > n1 && nums2.length > n2){
            if (nums1[n1]<nums2[n2]){
                nums[i] = nums1[n1];
                n1++;
                i++;
            }else if (nums1[n1]>nums2[n2]){
                nums[i] = nums2[n2];
                n2++;
                i++;
            }else{
                nums[i] = nums1[n1];
                nums[i+1] = nums2[n2];
                n1++;
                n2++;
                i=i+2;
            }
        }

        while (nums1.length > n1){
            nums[i] = nums1[n1];
            i++;
            n1++;
        }

        while (nums2.length >  n2){
            nums[i] = nums2[n2];
            i++;
            n2++;
        }
        /*double result;
        if (nums.length%2==0){
            double sum =  (nums[(nums.length/2)]+nums[nums.length/2-1]);
           result = sum/2.0;
        }else{
            result = nums[(nums.length-1)/2];
        }*/
        double result = (nums[(i-1)/2]+nums[i/2])/2.0;
        return result;
    }

    /**
     * 求中位数,二分搜索法来解
     *  1.将两个数组分割，再组合为left_part[]和right_part[]
     *  如果：
     *      left_part.length = right_part.length
     *      max(left_part) <= min(right_part)
     *  则中位数 = (max(left_part)+min(right_part))/2.0
     *  2.要保证上述条件需：
     *      mid1+mid2 = n1-mid1+n2-mid2(或mid1+mid2 = n1-mid1+n2-mid2+1)
     *      如果n2>n1,则mid1 = 0~n1,mid2=(n1+n2+1)/2 - mid1（必须确保 mid2不是负数。如果 n1>n2,那么mid2将可能是负数，而这会造成错误的答案。）
     *  以及
     *      num2[mid2-1] <= num1[mid1] && num1[mid1-1] <= num2[mid2]
     *
     *  所以，我们的目标就是在【0，n1】中寻找mid1，并计算mid2 = (n1+n2+1)/2-mid1
     *
     *  分析：
     * @param nums1 长度小的数组
     * @param nums2 长度大的数组
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //分别获取两个数组的长度
        int n1 = nums1.length, n2 = nums2.length;
        //将数组长度小的放在第一个
        if (n1 > n2) return findMedianSortedArrays(nums2,nums1);

        //mid1的所有可能值
        int min = 0, max = n1;
        while (min <= max) {
            int mid1 = (min + max) / 2;
            int mid2 = (n1 + n2+1)/2 - mid1;

            //因为两个数组都是排好序的，所以不考虑同数组左右两侧的大小问题
            //如果：第二个数组左侧最大，大于第一个数组的右侧最小
            //那么，第二个数组往左走一个，第一个数组的右侧往右走一个
            //即：mid1要增大，mid2要减小
            if (mid1 < max  && nums2[mid2-1]>nums1[mid1]){
                min = min+1;//mid1太小了
             //如果：第一个数组左侧最大，大于第二个数组右侧最小
             //那么，第一个数组的左侧往左走一个，第二个数组的右侧往右走一个
             //即：mid1要减小
            }else if (mid1 > min && nums1[mid1 - 1] > nums2[mid2]){
                max = max -1;//mid1太大了
            //如果：第一个数组左侧最大，小于第二个数组左侧最小
            //或者，第二个数组左侧最大，小于第一个数组右侧最小，都满足我们的要求
            }else{
                int max_left_part,min_right_part;
                if (mid1 == 0){
                    max_left_part = nums2[mid2-1];
                }else if (mid2 == 0){
                    max_left_part = nums1[mid1-1];
                }else{
                    max_left_part = Math.max(nums1[mid1 - 1],nums2[mid2 -1]);
                }

                if ((n1+n2)%2 ==1){
                    return max_left_part;
                }
                if (mid1 == n1){
                    min_right_part = nums2[mid2];
                }else if (mid2 == n2){
                    min_right_part = nums1[mid1];
                }else{
                    min_right_part = Math.min(nums1[mid1],nums2[mid2]);
                }

                return (max_left_part+min_right_part)/2.0;

            }
        }
        return -1;
    }

    public static void main(String[] args){
        int[] a = {1,2,3,4};
        int[] b = {3,5};
        System.out.println(findMedianSortedArrays(a,b));
    }
}
